package test_3_2;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

/**
 * 其它非基于比较的排序*/
public class Sort {
	/**
	 * 计数排序
	 * 时间复杂度：
	 * 		O(MAX(N,范围))
	 * 空间复杂度：
	 * 		O（范围）
	 * 稳定性：
	 * 		稳定（但是我这种实现是不稳定的）*/
	public static void countSort(int[] array) {
		//求最大值
		int max = array[0];
		int min = array[0];
		for(int i = 1; i < array.length; i++) {
			if(array[i]>max) {
				max = array[i];
			}
			if(array[i]<min) {
				min = array[i];
			}
		}
		
		//创建计数数组
		int[] tmp = new int[max-min+1];
		for(int i = 0; i < array.length; i++) {
			tmp[array[i]-min]++;
		}
		
		//将已排序的数值拷贝☞array数组
		int k = 0;
		for(int i = 0; i < tmp.length; i++) {
			while(tmp[i]!=0) {
				array[k++] = min+i;
				tmp[i]--;
			}
		}
	}
	
	/**
	 * 基数排序
	 * 时间复杂度：
	 *		O(N^2)
	 * 空间复杂度：
	 * 		O(N)
	 * 稳定性：
	 * 		不稳定
	 * */
	public static void radixSort(int[] array) {
		//创建一个桶
		Queue<Integer>[] bucket = new Queue[10];
		for(int i = 0; i < bucket.length; i++) {
			bucket[i] = new LinkedList<Integer>();
		}
		
		//求最大值
		int max = array[0];
		for(int i = 1; i < array.length; i++) {
			if(array[i]>max) {
				max = array[i];
			}
		}
		
		int div = 10;
		while(max*10 !=0) {
			for(int i = 0; i < array.length; i++) {
				int index = array[i]%div;
				while(index>10) {
					index/=10;
				}
				bucket[index].offer(array[i]);
			}
			int k = 0;
			for(int i = 0; i < bucket.length; i++) {
				while(!bucket[i].isEmpty()) {
					array[k++] = (int)bucket[i].poll();
				}
			}
			max/=10;
			div*=10;
		}
	}
}
